With the advent and increasing popularity of multi-processor, multi-thread systems, new problems of resource sharing have arisen. When multiple concurrently executing threads try to write to a resource at the same time, conflicts known as race conditions may ensue. To overcome these difficulties, data structures such as semaphore locks have been associated with shared resources to allow one thread to access and write to the resource at a time. The use of locks has also given rise to other difficulties, however. If a thread holding a lock doesn't release the lock, processing on the system may be unduly slowed or halted.
To overcome the difficulties of locks, many lock-free data structures have been proposed. A lock-free structure guarantees that when multiple threads operate simultaneously on the structure, at least one thread will complete its task in a finite number of steps. Lock-free structures have also proven susceptible to data coherence issues, such as the ABA problem. The ABA problem occurs when a thread is using a resource which is supposed to be deallocated, but which has not yet been deallocated.